package cn.z2huo.algorithm.sort.swapSort.quickSort;

//快速排序
public class SortQuick2 {
	static int demo = 0;
	
	public void quickSort(int[] array, int l, int h) {
		//low和high的作用是当结束一趟排序之后判断是否可以再在轴的两边的子序列进行排序。
		int low = l;
		int high = h;
		int cenPos;		//轴索引
		int cenValue;	//轴值
		int demo2 = 0;
		int demo3 = 0;
		
		cenPos = low;
		cenValue = array[low];
		//while中进行完一趟排序
		while(low < high) {
			//从高位找出比轴小的值所在位置
			while(low < high && array[high]	>= cenValue) {
				high --;
			}
			//找到位置之后进行交换
			if(low < high) {
				array[cenPos] = array[high];
				cenPos = high;
				low ++;
			}
			//从低位找出比轴值大的值所在位置
			while(low < high && array[low] <= cenValue) {
				low ++;
			}
			//找到位置之后进行交换
			if(low < high) {
				array[cenPos] = array[low];
				cenPos = low;
				high --;
			}
		}
		//由于前期只是知道轴值的位置，在进行完一趟排序之后，将之前保存好的轴值赋予最后所在位
		array[cenPos] = cenValue;

		demo ++;
		System.out.printf("完成了第%d趟排序！",demo);
		for(int i=0; i<array.length; i++) {
			System.out.printf("%d ",array[i]);
		}
		System.out.println();
		
		//判断是否可以再在轴的左右子序列中递归进行排序。
		if(low > l) {
			demo2 ++;
			System.out.printf("左边%d   ",demo2);
			quickSort(array, l, cenPos-1);
		}
		if(high < h) {
			demo3 ++;
			System.out.printf("右边%d   ",demo3);
			quickSort(array, cenPos+1, h);
		}
	}
	// 11,13,2,34,55,9,44,122,32,2,9
	//第一趟 
	// 9 13 2 34 55 9 44 122 32 2 11
	// 9 11 2 34 55 9 44 122 32 2 13
	// 9 2 2 34 55 9 44 122 32 11 13
	// 9 2 2 11 55 9 44 122 32 34 13
	// 9 2 2 9 55 11 44 122 32 34 13
	// 9 2 2 9 11 55 44 122 32 34 13
	// 结束时 l 0  h array.length-1
	//第二趟
	// 轴左边
	// 2 2 9 9
	// 轴右边
	public static void main(String[] args) {
		int[] array = {11,13,2,34,55,9,44,122,32,2,9};
		SortQuick2 sq = new SortQuick2();
		sq.quickSort(array, 0, array.length-1);
		
		for(int i=0; i<array.length; i++) {
			System.out.printf("%d ",array[i]);
		}
		System.out.println();
	}
}